package com.sort;

import java.util.ArrayList;

public class RadixSort {
    public void sort(int[] arr){
//        升级版桶排序，利用桶进行基数排序LSD
        int len = arr.length;
        int max = arr[0];
        for (int i : arr){
            max = Math.max(max,i);
        }
//        当前排序位置
        int location = 1;
//        桶列表
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
//        创建10个桶
        for (int i=0;i<10;i++){
            bucketList.add(new ArrayList<>());
        }
        while (true){
//            判断是否排完，当10的n次方大于数组最大值
            int dd = (int) Math.pow(10,(location-1));
            if(max<dd) break;
//            数据入桶
            for(int i=0;i<len;i++){
                int num = (arr[i]/dd)%10;
                bucketList.get(num).add(arr[i]);
            }
//            写回数组
            int index = 0;
            for (int i=0;i<10;i++){
                int size = bucketList.get(i).size();
                for (int j=0;j<size;j++){
                    arr[index++] = bucketList.get(i).get(j);
                }
//                清空桶数据
                bucketList.get(i).clear();
            }
            location++;
        }
    }
}






